Image compression and hybrid video compression consists of partitioning a frame into blocks, predicting each block and transforming the residual error using a block transform. Video compression algorithms generally use motion compensation from previous frames, whereas image compression algorithms may use previously encoded neighboring blocks to generate the prediction or may not use prediction at all. After transformation, the generated coefficients are quantized and then entropy coded.
The DCT has been the transform of choice for a long time for image and video compression due to its successful compaction of the correlations that exist in natural images. Although the DCT is in general successful, it fails when there are singularities (i.e., edges) in the block that is being transformed. Such a block contains a strong edge that is not aligned in the horizontal or vertical direction. As a result, the DCT generates many non-zero coefficients to represent the block, which increases the required bitrate.
There are a number of prior art solutions, but these have drawbacks. Some drawbacks of prior art solutions can be summarized as follows. Some of the prior solutions are based on wavelets, which are not block based and are not suitable for use in state-of-the-art block based video and image codecs. Prior art solutions based on wavelets also do not provide finely granular decompositions in frequency, i.e., their frequency selectivity is limited, which may adversely affect compression performance. Another group of prior solutions use prediction from previously decoded portions of the data. These set of algorithms are not suitable for use in a video compression setting where the residual signal is not correlated beyond motion compensation block boundaries. Another group of related prior solutions also train the transforms. However, these solutions put a constraint on the transform such that directionality is preserved. This may not necessarily be true in a rate distortion optimal sense.